package main

import (
	"container/list"
	"fmt"
)

type LRUCache struct {
	// 最大容量
	cap int
	// 哈希表
	lrumap map[int]*list.Element
	// 双链表
	cache list.List
}

func Constructor(capacity int) LRUCache {
	var lrucache LRUCache
	lrucache.cap = capacity
	lrumap := make(map[int]*list.Element)
	lrucache.lrumap = lrumap
	return lrucache
}

// 以node的形式变成element的value
type Node struct {
	key, val int
}

// node的构造函数
func NConstructor(key, val int) Node {
	var node Node
	node.key = key
	node.val = val
	return node
}

// 将map中key代表的这个节点变成列表中最后（最近使用）一个
func (lr *LRUCache) makeRecently(key int) {
	// 先通过map获取
	element := lr.lrumap[key]
	// 把它移到链表末尾
	lr.cache.MoveToBack(element)
	// // 再在链表中删除
	// lr.cache.Remove(element)
	// // 最后添加链表到末尾
	// // 这里可能有问题
	// lr.cache.PushBack(element.Value)
}

// 添加最近使用的元素
func (lr *LRUCache) addRecently(key, val int) {
	// 加进链表
	temp := NConstructor(key, val)
	x := lr.cache.PushBack(temp)
	// 更新map
	lr.lrumap[key] = x
}

// 删除某一个key
func (lr *LRUCache) deleteKey(key int) {
	x := lr.lrumap[key]
	lr.cache.Remove(x)
	delete(lr.lrumap, key)
}

// 删除最久未使用的元素
func (lr *LRUCache) removeLeastRecently() {
	// 链表头部的就是最久未使用的
	x := lr.cache.Front()
	lr.cache.Remove(x)
	val := x.Value.(Node)
	// 同步删除map中的值
	delete(lr.lrumap, val.key)
}

func (this *LRUCache) Get(key int) int {
	_, exist := this.lrumap[key]
	if exist {
		this.makeRecently(key)
		temp := this.lrumap[key].Value.(Node)
		return temp.val
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	_, exist := this.lrumap[key]
	if exist {
		//删除旧数据
		this.deleteKey(key)
		// 添加新数据
		this.addRecently(key, value)
		return
		// 有个问题：
		// 不可以直接提升这个节点到末尾吗？
	}
	if this.cap == this.cache.Len() {
		this.removeLeastRecently()
	}
	// 添加为最近使用的元素
	this.addRecently(key, value)
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */
func main() {

	lru := Constructor(2)
	lru.Put(1, 1)
	lru.Put(2, 2)
	fmt.Println(lru.Get(1))
	lru.Put(3, 3)
	fmt.Println(lru.Get(2))
	lru.Put(4, 4)
	fmt.Println(lru.Get(1))
	fmt.Println(lru.Get(3))
	fmt.Println(lru.Get(4))
	// test := DConstructor()
	// node1 := NConstructor(1, 1)
	// test.addList(node1)
	// fmt.Print(&test, test.dlsize())
	// node2 := NConstructor(2, 2)
	// test.addList(node2)
	// fmt.Print(test, test.dlsize())
	// node3 := NConstructor(3, 3)
	// test.addList(node3)
	// fmt.Print(test, test.dlsize())
	// node4 := NConstructor(4, 4)
	// test.addList(node4)
	// fmt.Print(test, test.dlsize())
	// test.removeFirst()
	// fmt.Print(test, test.dlsize())
	// test.remove(node3)
	// fmt.Print(test, test.dlsize())

}
